#include <iostream>
#include <stack>

using namespace std;

// problem 4
class Tower {
public:
  Tower(size_t id) : _id(id) {}

  size_t getId() const { return _id; }
  
  void add(size_t disk) {
    if (!_disks.empty() && _disks.top() < disk) {
      throw "you can only stack smaller disk on the top";
    }
    _disks.push(disk);
  }

  void moveTopTo(Tower& t) {
    if (_disks.empty())
      throw "no disk to move";
    size_t disk = _disks.top();
    t.add(disk);
    _disks.pop();
    cout << "Moved disk " << disk << " from tower " << getId() << " to tower " << t.getId() << endl;
  }

  void moveDisks(size_t num, Tower& destination, Tower& buffer) {
    if (num > 0) {
      moveDisks(num-1, buffer, destination);
      moveTopTo(destination);
      buffer.moveDisks(num-1, destination, *this);
    }
  }

private:
  size_t _id;
  stack<size_t> _disks;
};

// problem 6
template<typename T>
stack<T> sort_stack(stack<T>& s) {
  stack<T> sorted;
  while (!s.empty()) {
    T elem = s.top();
    s.pop();
    while (!sorted.empty() && sorted.top() < elem) {
      s.push(sorted.top());
      sorted.pop();
    }
    sorted.push(elem);
  }
  return sorted;
}

template<typename T>
void print_stack(stack<T>& s) {
  while (!s.empty()) {
    cout << s.top() << " ";
    s.pop();
  }
  cout << endl;
}

int main() {
  try {
    cout << "Problem 4:" << endl;
    Tower towers[] = { Tower(0), Tower(1), Tower(2) };
    size_t num = 3;
    for (size_t i = num; i > 0; i--) 
      towers[0].add(i);
    cout << "stacked " << num << " disks on tower 0" << endl;
    towers[0].moveDisks(num, towers[2], towers[1]);
    cout << endl;
  }
  catch(const char* str) {
    cout << str << endl;
  }

  cout << "Problem 6:" << endl;
  stack<int> s; s.push(6); s.push(3); s.push(7); s.push(1); s.push(4);
  s = sort_stack(s);
  print_stack(s);
  cout << endl;

  return 0;
}
